/*
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

*/
/**
 * @author yu
 * @date 2025年05月02日 23:25
 *//*


class _10_BFS {
    // 表示四个方向
    private static final int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};


    // grid 是地图，也就是一个二维数组
    // visited 标记访问过的节点，不要重复访问
    // x, y 表示开始搜索节点的下标
    public static void bfs(int[][] grid, boolean[][] visited, int x, int y) {
        // 定义队列
        Queue<int[]> que = new LinkedList<>();

        // 起始节点加入队列
        que.add(new int[]{x, y});
        // 只要加入队列，立刻标记为访问过的节点
        visited[x][y] = true;

        // 开始遍历队列里的元素
        while (!que.isEmpty()) {
            // 从队列取元素
            int[] cur = que.poll();
            int curx = cur[0];
            int cury = cur[1]; // 当前节点坐标

            // 开始向当前节点的四个方向（左右上下）去遍历
            for (int i = 0; i < 4; i++) {
                // 获取周边四个方向的坐标
                int nextx = curx + dir[i][0];
                int nexty = cury + dir[i][1];

                // 坐标越界了，直接跳过
                if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) {
                    continue;
                }

                // 如果节点没被访问过
                if (!visited[nextx][nexty]) {
                    // 队列添加该节点为下一轮要遍历的节点
                    que.add(new int[]{nextx, nexty});
                    // 只要加入队列立刻标记，避免重复访问
                    visited[nextx][nexty] = true;
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("输入行数 列数: ");
        int rows = scanner.nextInt(), cols = scanner.nextInt();
        scanner.nextLine(); // 消耗换行符

        int[][] grid = new int[rows][cols]; // 改为 int 类型
        boolean[][] visited = new boolean[rows][cols];

        System.out.println("输入地图数据（每行" + cols + "个整数，用空格分隔）:");
        for (int i = 0; i < rows; i++) {
            String[] parts = scanner.nextLine().split(" ");
            for (int j = 0; j < cols; j++) {
                grid[i][j] = Integer.parseInt(parts[j]); // 解析为整数
            }
        }

        System.out.print("输入起始坐标（行 列）: ");
        int startX = scanner.nextInt(), startY = scanner.nextInt();

        bfs(grid, visited, startX, startY);

        System.out.println("\n访问结果:");
        */
/*for (boolean[] row : visited) {
            for (boolean flag : row) {
                System.out.print(flag ? "T " : "F ");
            }
            System.out.println();
        }*//*

        System.out.println("\nBFS 遍历顺序（坐标 -> 数值）:");
        for (int[] coord : que) {
            int x = coord[0];
            int y = coord[1];
            System.out.printf("(%d, %d) -> %d%n", x, y, grid[x][y]);
        }


        scanner.close();
    }
}
*/

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author yu
 * @date 2025年05月02日 23:25
 */
class _10_BFS {
    private static final int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    // 使用 List 存储遍历顺序（比直接使用队列更便于输出）
    private static final List<int[]> result = new ArrayList<>();

    public static void bfs(int[][] grid, boolean[][] visited, int x, int y) {
        Queue<int[]> que = new LinkedList<>();
        que.offer(new int[]{x, y});
        visited[x][y] = true;
        result.add(new int[]{x, y}); // 记录起始节点

        while (!que.isEmpty()) {
            int[] cur = que.poll();
            int curX = cur[0];
            int curY = cur[1];

            for (int[] d : dir) {
                int nextX = curX + d[0];
                int nextY = curY + d[1];

                if (isValid(grid, nextX, nextY) && !visited[nextX][nextY]) {
                    visited[nextX][nextY] = true;
                    que.offer(new int[]{nextX, nextY});
                    result.add(new int[]{nextX, nextY}); // 记录遍历顺序
                }
            }
        }
    }

    private static boolean isValid(int[][] grid, int x, int y) {
        return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("输入行数 列数: ");
        int rows = scanner.nextInt(), cols = scanner.nextInt();
        scanner.nextLine();

        int[][] grid = new int[rows][cols];
        boolean[][] visited = new boolean[rows][cols];

        System.out.println("输入地图数据（每行" + cols + "个整数，用空格分隔）:");
        for (int i = 0; i < rows; i++) {
            String[] parts = scanner.nextLine().split(" ");
            for (int j = 0; j < cols; j++) {
                grid[i][j] = Integer.parseInt(parts[j]);
            }
        }

        System.out.print("输入起始坐标（行 列）: ");
        int startX = scanner.nextInt(), startY = scanner.nextInt();

        bfs(grid, visited, startX, startY);

        // 输出队列遍历顺序（坐标及对应数值）
        System.out.println("\nBFS 遍历顺序（坐标 -> 数值）:");
        for (int[] coord : result) {
            int x = coord[0];
            int y = coord[1];
            System.out.printf("(%d, %d) -> %d%n", x, y, grid[x][y]);
        }

        // 提取数值并拼接成一行
        List<Integer> values = new ArrayList<>();
        for (int[] coord : result) {
            values.add(grid[coord[0]][coord[1]]);
        }

        System.out.println("\n直接打印 values 列表：");
        System.out.println(values); // 输出：[5, 4, 6, 2, 8, 1, 3, 7, 9]


        String oneLineOutput = values.stream()
                .map(String::valueOf)
                .collect(Collectors.joining(" "));

        System.out.println("\nBFS 遍历数值（一行输出）:");
        System.out.println(oneLineOutput);

        scanner.close();
    }
}
